﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AMS.LCM
{
    public class PrimeFactors
    {
        private Dictionary<long, int> _factors; // prime, count

        public int this[long l]
        {
            get
            {
                if (_factors.ContainsKey(l))
                    return _factors[l];
                return 0;
            }
        }

        public IEnumerable<long> Primes
        {
            get { return _factors.Keys; }
        }
	
        public PrimeFactors()
        {
            this._factors = new Dictionary<long, int>();
        }

	    public PrimeFactors(long value)
	    {
            this._factors = Factor(value);
	    }
	
	    public long Value
	    {
		    get
		    {
			    // loop over primes and raise to powers
                long i = 1;
                foreach (long p in _factors.Keys)
                {
                    i *= (long)Math.Pow(p, _factors[p]);
                }
                return i;
		    }
		    set
		    {
			    this._factors = Factor(value);
		    }
	    }

        public void Add(long prime, int count = 1)
        {
            if (!_factors.ContainsKey(prime))
                _factors.Add(prime, 0);
            _factors[prime] += count;
        }

        public void Combine(long prime, int count)
        {
            if (!_factors.ContainsKey(prime))
                _factors.Add(prime, 0);
            _factors[prime] = count > _factors[prime] ? count : _factors[prime];
        }

        public void Combine(PrimeFactors other)
        {
            foreach (long p in other.Primes)
                this.Combine(p, other[p]);
        }

        public static Dictionary<long, int> Factor(long n)
        {
            if (n < 2)
                throw new ArgumentOutOfRangeException("cannot be less than 2");

            List<long> primes = MathHelper.GetPrimes(n);
            Dictionary<long, int> factors = new Dictionary<long, int>();

            Factor(n, factors, primes);

            return factors;
        }

        private static void Factor(long n, Dictionary<long, int> factors, List<long> primes)
        {
            foreach (long prime in primes) // primes is a sorted list of all primes between 2 and n
            {
                //if (prime >= n / 2)
                //    break;

                if (n % prime == 0)
                {
                    Add(factors, prime, 1);
                    n = n / prime;
                    Factor(n, factors, primes); // recursively factor the result
                    break;
                }
            }
        }

        private static void Add(Dictionary<long, int> factors, long l, int count = 1)
        {
            if (!factors.ContainsKey(l))
                factors.Add(l, 0);
            factors[l] += count;
        }
	
	    public static PrimeFactors Combine(PrimeFactors a, PrimeFactors b)
	    {
            PrimeFactors f = new PrimeFactors();
            List<long> allPrimes = new List<long>(a.Primes);
            foreach (long p in b.Primes)
            {
                if (!allPrimes.Contains(p))
                    allPrimes.Add(p);
            }

            allPrimes.Sort();

            foreach (long p in allPrimes)
            {
                int c = a[p] > b[p] ? a[p] : b[p];
                f.Add(p, c);
            }
            return f;
	    }
    }
}
